package 数组;

/**
 * @Author zxl
 * @Date 2022/1/1 16:09
 * @Desc 在一个有序无重复元素的数组nums中，寻找一个元素target，如果找到则返回target下标，否则返回-1
 */
public class 二分查找 {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 9, 9, 10};
        int target1 = 9;
        int target2 = 12;
//        System.out.println("search:" + target1 + ",index:" + search2(nums, target1));
//        System.out.println("search:" + target2 + ",index:" + search2(nums, target2));
        System.out.println("search:" + target2 + ",index:" + searchRange(nums, target1));

    }

    /**
     * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
     * 如果数组中不存在目标值 target，返回 [-1, -1]。
     * 时间复杂度为 O(log n)
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] searchRange(int[] nums, int target) {
        int leftIndex = searchLeft(nums, target);
        int rightIndex = searchRight(nums, target);
        return new int[]{leftIndex, rightIndex};

    }

    // 1233356
    public static int searchLeft(int[] nums, int target) {
        int leftIndex = 0;
        int rightIndex = nums.length - 1;
        while (leftIndex <= rightIndex) {
            int mindIndex = (rightIndex + leftIndex) / 2;
            if (target <= nums[mindIndex]) {
                rightIndex = mindIndex - 1;
            } else if (target > nums[mindIndex]) {
                leftIndex = mindIndex + 1;
            }
        }
        return leftIndex;
    }

    public static int searchRight(int[] nums, int target) {
        int leftIndex = 0;
        int rightIndex = nums.length - 1;
        while (leftIndex <= rightIndex) {
            int mindIndex = (rightIndex + leftIndex) / 2;
            if (target < nums[mindIndex]) {
                rightIndex = mindIndex - 1;
            } else if (target >= nums[mindIndex]) {
                leftIndex = mindIndex + 1;
            }
        }
        return rightIndex;
    }


    /**
     * 搜索插入位置
     *
     * @param nums
     * @param target
     * @return
     */
    public static int search2(int[] nums, int target) {
        int leftIndex = 0, rightIndex = nums.length - 1;
        int mindIndex = 0;
        while (leftIndex <= rightIndex) {
            mindIndex = (rightIndex + leftIndex) / 2;
            if (nums[mindIndex] < target) {
                leftIndex = mindIndex + 1;
            } else if (nums[mindIndex] > target) {
                rightIndex = mindIndex - 1;
            } else {
                return mindIndex;
            }
        }
        if (nums[mindIndex] < target) {
            return mindIndex + 1;
        } else {
            return mindIndex;
        }
    }


    /**
     * 二分查找
     *
     * @param nums
     * @param target
     * @return 0123456
     */
    public static int search(int[] nums, int target) {
        int leftIndex = 0;
        int rightIndex = nums.length - 1;
        while (leftIndex <= rightIndex) {
            int middleIndex = (leftIndex + rightIndex) / 2;
            if (nums[middleIndex] > target) {
                rightIndex = middleIndex - 1;
            } else if (nums[middleIndex] < target) {
                leftIndex = middleIndex + 1;
            } else {
                return middleIndex;
            }
        }
        return -1;
    }
}
